﻿/*
 * Module Name: AVLTree.cs
 * 
 * Purpose: This is an implementation of a balanced AVL tree
 * 
 * Created by: Chris Tisdale
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace Common_Code.Trees
{
    class AVLTree<T> : Tree<T> where T : IComparable
    {
        /*
         * These are the private variables used throught the function
         */
        private Node<T> headNode;
        private T[] treeInArray;
        private bool change = true;
        private int size = 0;

        /*
         * Name: AVLTree
         * 
         * Parameters: Node<T> head
         * 
         * Returns: An AVLTree Object
         * 
         * Purpose: Creates an AVL tree
         */
        public AVLTree(Node<T> head)
        {
            headNode = head;
        }

        /*
         * Name: AVLTree
         * 
         * Parameters: None
         * 
         * Returns: An AVLTree Object
         * 
         * Purpose: Creates an AVL tree
         */
        public AVLTree()
        {
            headNode = null;
        }

        /*
         * Name: AddNode
         * 
         * Parameters: T item
         * 
         * Returns: None
         * 
         * Purpose: Adds an item to the tree
         */
        public void AddNode(T item)
        {
            Insert(headNode, item);
        }

        /*
         * Name: Insert
         * 
         * Parameters: Node<T> node
         *             T item
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function that returns the head Node which contains the newly added item
         */
        private Node<T> Insert(Node<T> node, T item)
        {
            if (node == null)  //The item is not in the tree
            {
                change = true;
                size++;
                node = new Node<T>(item);
                node.SetHeight(0);
                return node;
            }
            else
            {
                var comp = item.CompareTo(node.GetItem());
                if (comp == 0) //The item is already in the tree don't add
                {}
                else if (comp > 0)
                {
                    node.SetRightNode(Insert(node.GetRightNode(), item));
                    if ((GetHeight(node.GetRightNode()) - GetHeight(node.GetLeftNode())) == 2)
                    {
                        if (item.CompareTo((node.GetRightNode()).GetItem()) > 0)
                        {
                            node = RotateWithRightChild(node);
                        }
                        else
                        {
                            node = DoubleWithRightChild(node);
                        }
                    }
                }
                else
                {
                    node.SetLeftNode(Insert(node.GetLeftNode(), item));
                    if ((GetHeight(node.GetLeftNode()) - GetHeight(node.GetRightNode())) == 2)
                    {
                        if (item.CompareTo((node.GetLeftNode()).GetItem()) < 0)
                        {
                            node = RotateWithLeftChild(node);
                        }
                        else
                        {
                            node = DoubleWithLeftChild(node);
                        }
                    }
                }
                node.SetHeight(Math.Max(GetHeight(node.GetLeftNode()), GetHeight(node.GetRightNode())) + 1);
                return node;
            }
        }

        /*
         * Name: GetHeight
         * 
         * Parameters: Node<T> node
         * 
         * Returns: int
         * 
         * Purpose: This is a method will return the height of the tree and handles the null exception
         */
        private int GetHeight(Node<T> node)
        {
            return node == null ? -1 : node.GetHeight();
        }

        /*
         * Name: RotateWithLeftChild
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a method ment to rotate the left child of a node
         */
        private Node<T> RotateWithLeftChild(Node<T> node)
        {
            var temp = node.GetLeftNode();
            node.SetLeftNode(temp.GetRightNode());
            temp.SetRightNode(node);
            node.SetHeight(Math.Max(GetHeight(node.GetLeftNode()), GetHeight(node.GetRightNode())) + 1);
            temp.SetHeight(Math.Max(GetHeight(temp.GetLeftNode()), GetHeight(node)) + 1);
            return temp;
        }

        /*
         * Name: RotateWithRightChild
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a method ment to rotate the right child of a node
         */
        private Node<T> RotateWithRightChild(Node<T> node)
        {
            var temp = node.GetRightNode();
            node.SetRightNode(temp.GetLeftNode());
            temp.SetLeftNode(node);
            node.SetHeight(Math.Max(GetHeight(node.GetLeftNode()), GetHeight(node.GetRightNode())) + 1);
            temp.SetHeight(Math.Max(GetHeight(temp.GetRightNode()), GetHeight(node)) + 1);
            return temp;
        }

        /*
         * Name: DoubleWithLeftChild
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a method ment to rotate the left child of a node twice
         */
        private Node<T> DoubleWithLeftChild(Node<T> node)
        {
            node.SetLeftNode(RotateWithRightChild(node.GetRightNode()));
            return RotateWithLeftChild(node);
        }

        /*
         * Name: DoubleWithRightChild
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a method ment to rotate the right child of a node twice
         */
        private Node<T> DoubleWithRightChild(Node<T> node)
        {
            node.SetRightNode(RotateWithLeftChild(node.GetLeftNode()));
            return RotateWithRightChild(node);
        }

        /*
         * Name: DeleteNode
         * 
         * Parameters: T item
         * 
         * Returns: None
         * 
         * Purpose: If the item was removed true is returned, else false is returned
         *          This algorithm assumes the Tree is already balanced
         */
        public void DeleteNode(T item)
        {
            throw new NotImplementedException();
        }

        /*
         * Name: Delete
         * 
         * Parameters: Node<T> node
         *             T item
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function that returns the head Node which contains the node containing item removed
         */
        private Node<T> Delete(Node<T> node, T item)
        {
            if (node == null)  //The item is not in the tree
            {
                return null;
            }
            else
            {
                var comp = item.CompareTo(node.GetItem());
                if (comp == 0) //found it now remove
                {
                    if (node.GetLeftNode() == null && node.GetRightNode() == null)
                    {
                        return null;
                    }
                    else if (node.GetLeftNode() == null)
                    {
                        return node.GetRightNode();
                    }
                    else if (node.GetRightNode() == null)
                    {
                        return node.GetLeftNode();
                    }
                    else //need to implement
                    {
                        if (GetHeight(node.GetLeftNode()) > GetHeight(node.GetRightNode()))
                        {
                            ReplaceWithRightMostNode(node);
                        }
                        else
                        {
                            ReplaceWithLeftMostNode(node);
                        }
                        if ((GetHeight(node.GetLeftNode()) - GetHeight(node.GetRightNode())) == 2)
                        {
                            if (item.CompareTo((node.GetLeftNode()).GetItem()) < 0)
                            {
                                node = RotateWithLeftChild(node);
                            }
                            else
                            {
                                node = DoubleWithLeftChild(node);
                            }
                        }
                        //need to add balancing logic
                    }
                }
                else if (comp > 0)
                {
                    node.SetRightNode(Insert(node.GetRightNode(), item));
                    //need to add balancing logic
                }
                else
                {
                    node.SetLeftNode(Insert(node.GetLeftNode(), item));
                    //need to add balancing logic
                }
            }
            node.SetHeight(Math.Max(GetHeight(node.GetLeftNode()), GetHeight(node.GetRightNode())) + 1); //this needs to be updated
            return node;
        }

        /*
         * Name: ReplaceWithLeftMostNode
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: 
         */
        private Node<T> ReplaceWithLeftMostNode(Node<T> node)
        {
            if (node == null)
            {
                return null;
            }

            throw new NotImplementedException();
        }

        /*
         * Name: BalanceTree
         * 
         * Parameters: Node<T> node
         * 
         * Returns: Node<T>
         * 
         * Purpose: 
         */
        private Node<T> ReplaceWithRightMostNode(Node<T> node)
        {
            if (node == null)
            {
                return null;
            }

            throw new NotImplementedException();
        }

        /*
         * Name: FindItem
         * 
         * Parameters: T item
         * 
         * Returns: Node
         * 
         * Purpose: This gives you all of the elements from the tree
         */
        public Node<T> FindItem(T item)
        {
            return FindRec(headNode, item);
        }

        /*
         * Name: FindRec
         * 
         * Parameters: Node<T> node
         *             T item
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function that returns the Node which contains the item
         */
        private Node<T> FindRec(Node<T> node, T item)
        {
            if (node == null)
                return null;
            var comp = item.CompareTo(node.GetItem());
            if (comp > 0)
            {
                return FindRec(node.GetRightNode(), item);
            }
            else if (comp < 0)
            {
                return FindRec(node.GetLeftNode(), item);
            }
            else
            {
                //found item
                return node;
            }
        }

        /*
         * Name: ToArray
         * 
         * Parameters: NA
         * 
         * Returns: T[]
         * 
         * Purpose: This gives you all of the elements from the tree
         */
        public T[] ToArray()
        {
            if (change)
            {
                treeInArray = new T[size];
                CreateArray(headNode, 0);
                change = false;
            }
            return treeInArray;
        }

        /*
         * Name: CreateArray
         * 
         * Parameters: Node<T> node
         *             int loc
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function creates an array from the tree
         */
        private Node<T> CreateArray(Node<T> node, int loc)
        {
            if (node == null)
                return null;
            CreateArray(node.GetLeftNode(), loc);
            treeInArray[loc] = node.GetItem();
            loc++;
            CreateArray(node.GetRightNode(), loc);
            return node;
        }

        /*
         * Name: IsBalanced
         * 
         * Parameters: Node<T> node
         * 
         * Returns: int bal
         * 
         * Purpose: This is a recursive function that will determine if the tree is balanced.
         *          If the tree is left heavy -1 will be returned.  If the tree is right heavy
         *          1 will be returned.  If the tree is balanced 0 will be returned.
         */
        private int IsBalanced(Node<T> node)
        {
            throw new NotImplementedException();
        }
    }
}
